package com.dycong.common.leetcode.sort;

import java.util.Arrays;

/**
 * @author dycong
 * @date 2019/12/5 9:14
 */
public class QuickSort {

    public static void main(String[] args) {
        QuickSort bubbleSort = new QuickSort();
//        int[] ints = new int[]{1, 2, 5, 8, 6, 5, 9, 5, 55, 5};
//        int[] ints = new int[]{0};
//        int[] ints = new int[]{-1,2,-8,-10};
        int[] ints = new int[]{-74, 48, -20, 2, 10, -84, -5, -9, 11, -24, -91, 2, -71, 64, 63, 80, 28, -30, -58, -11, -44, -87, -22, 54, -74, -10, -55, -28, -46, 29, 10, 50, -72, 34, 26, 25, 8, 51, 13, 30, 35, -8, 50, 65, -6, 16, -2, 21, -78, 35, -13, 14, 23, -3, 26, -90, 86, 25, -56, 91, -13, 92, -25, 37, 57, -20, -69, 98, 95, 45, 47, 29, 86, -28, 73, -44, -46, 65, -84, -96, -24, -12, 72, -68, 93, 57, 92, 52, -45, -2, 85, -63, 56, 55, 12, -85, 77, -39};
          bubbleSort.sort(ints);
        System.out.println(Arrays.toString(ints));
    }

    public void sort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public void quickSort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = medium(a, left, right);
        if (right - left < 3) {
            swap(a, (left + right) / 2, right - 1);
            return;
        }
        int i = left + 1, j = right - 1 - 1;
        System.out.println("i:  " + i + "   j:  " + j);
        for (; ; ) {
            while (a[i] < pivot) {
                ++i;
//                if (i == j) {
//                    break;
//                }
            }
            while (a[j] > pivot) {
                --j;
//                if (i == j) {
//                    break;
//                }
            }

            if (i >= j) {
                break;
            }

            swap(a, i, j);
        }

        // while 中 i == j 判断会影响这里
        swap(a, i, right - 1);
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }

    /**
     * 取三数中值，并将三数排序，并将 中值移动到数组尾部
     *
     * @param a
     * @param left
     * @param right
     * @return
     */
    private int medium(int[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[left] > a[right]) {
            swap(a, left, right);
        }
        if (a[left] > a[center]) {
            swap(a, left, center);
        }
        if (a[right] < a[center]) {
            swap(a, right, center);
        }
        swap(a, center, right - 1);
        return a[right - 1];
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void bubbleSort(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }
}
